{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Break a Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: breakPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #破坏回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由小写英文字母组成的回文字符串&nbsp;<code>palindrome</code> ，请你将其中&nbsp;<strong>一个</strong> 字符用任意小写英文字母替换，使得结果字符串的 <strong>字典序最小</strong> ，且&nbsp;<strong>不是</strong>&nbsp;回文串。</p>\n",
    "\n",
    "<p>请你返回结果字符串。如果无法做到，则返回一个 <strong>空串</strong> 。</p>\n",
    "\n",
    "<p>如果两个字符串长度相同，那么字符串 <code>a</code> 字典序比字符串 <code>b</code> 小可以这样定义：在 <code>a</code> 和 <code>b</code> 出现不同的第一个位置上，字符串 <code>a</code> 中的字符严格小于 <code>b</code> 中的对应字符。例如，<code>\"abcc”</code> 字典序比 <code>\"abcd\"</code> 小，因为不同的第一个位置是在第四个字符，显然 <code>'c'</code> 比 <code>'d'</code> 小。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>palindrome = \"abccba\"\n",
    "<strong>输出：</strong>\"aaccba\"\n",
    "<strong>解释：</strong>存在多种方法可以使 \"abccba\" 不是回文，例如 \"<em><strong>z</strong></em>bccba\", \"a<em><strong>a</strong></em>ccba\", 和 \"ab<em><strong>a</strong></em>cba\" 。\n",
    "在所有方法中，\"aaccba\" 的字典序最小。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>palindrome = \"a\"\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>不存在替换一个字符使 \"a\" 变成非回文的方法，所以返回空字符串。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= palindrome.length &lt;= 1000</code></li>\n",
    "\t<li><code>palindrome</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [break-a-palindrome](https://leetcode.cn/problems/break-a-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [break-a-palindrome](https://leetcode.cn/problems/break-a-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abccba\"', '\"a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        #aaabaaa    k = 2 for i in range(3)\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return ''\n",
    "        k = n//2\n",
    "        for i in range(k):\n",
    "            if palindrome[i] != \"a\":\n",
    "                return palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "        return palindrome[:-1] + 'b'\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        def isPalindrome(s:str):\n",
    "            for i in range(0,len(s) // 2):\n",
    "                if s[i] != s[len(s)-i-1]:\n",
    "                    return False\n",
    "            return True\n",
    "        if len(palindrome) == 1:\n",
    "            return \"\"\n",
    "        for i in range(0,(len(palindrome) + 1) // 2):\n",
    "            if palindrome[i] == \"a\":\n",
    "                continue\n",
    "            s = palindrome[:i] + \"a\" + palindrome[i+1:]\n",
    "            if not isPalindrome(s):\n",
    "                return s\n",
    "        return palindrome[:len(palindrome)-1] + \"b\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return \"\"\n",
    "        hwc = list(palindrome)\n",
    "        flag = False\n",
    "        for i in range(n//2 + 1):\n",
    "            if hwc[i] != 'a' and (n % 2 == 0 or n % 2 != 0 and i != n // 2):\n",
    "                hwc[i] = 'a'\n",
    "                flag = True\n",
    "                break\n",
    "        if flag == False:\n",
    "            hwc[-1] = 'b'\n",
    "        return \"\".join(hwc)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        str_len = len(palindrome)\n",
    "        if str_len < 2:\n",
    "            return \"\"\n",
    "        for idx in range(str_len >> 1):\n",
    "            if palindrome[idx] > 'a':\n",
    "                return palindrome[:idx] + 'a' + palindrome[idx+1:]\n",
    "        return palindrome[:str_len-1] + 'b'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1: return \"\"\n",
    "        for i in range(n):\n",
    "            if palindrome[i] != 'a' and (n & 1 == 0 or i != n // 2):\n",
    "                return palindrome[:i] + 'a' + palindrome[i + 1:]\n",
    "        return palindrome[:-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return \"\"\n",
    "        hwc = list(palindrome)\n",
    "        flag = False\n",
    "        for i in range(n//2 + 1):\n",
    "            if hwc[i] != 'a' and (n % 2 == 0 or n % 2 != 0 and i != n // 2):\n",
    "                hwc[i] = 'a'\n",
    "                flag = True\n",
    "                break\n",
    "        if not flag:\n",
    "            hwc[-1] = 'b'\n",
    "        return \"\".join(hwc)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome) == 1:return ''\n",
    "        for i,char in enumerate(palindrome):\n",
    "            if char != 'a':\n",
    "                temp = palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "                if temp != temp[::-1]:\n",
    "                    return temp\n",
    "        if palindrome[-1] == 'a':\n",
    "            return palindrome[:-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return ''\n",
    "        l = list(palindrome)\n",
    "        for i, c in enumerate(l):\n",
    "            if c != 'a' and i != (n - 1) / 2:\n",
    "                l[i] = 'a'\n",
    "                break\n",
    "        else:\n",
    "            l[-1] = 'b'\n",
    "        return ''.join(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome) == 1:\n",
    "            return ''\n",
    "        l = list(palindrome)\n",
    "        for i, c in enumerate(l):\n",
    "            if c != 'a' and i != (len(l) - 1) / 2:\n",
    "                l[i] = 'a'\n",
    "                break\n",
    "        else:\n",
    "            l[-1] = 'b'\n",
    "        return ''.join(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome) == 1:\n",
    "            return ''\n",
    "        res = list(palindrome)\n",
    "        n = len(palindrome)\n",
    "        if res[:n // 2] == ['a'] * (n // 2):\n",
    "            res[-1] = 'b'            \n",
    "        else:\n",
    "            for i in range(n):\n",
    "                if res[i] != 'a':\n",
    "                    res[i] = 'a'\n",
    "                    break \n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return ''\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if palindrome[i] != 'a' and (n & 1 == 0 or i != n // 2):\n",
    "                return palindrome[:i] + 'a' + palindrome[i + 1:]\n",
    "        return palindrome[:-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return ''\n",
    "        l = list(palindrome)\n",
    "        for i in range(n >> 1):\n",
    "            if l[i] != 'a':\n",
    "                l[i] = 'a'\n",
    "                break\n",
    "        else:\n",
    "            l[-1] = 'b'\n",
    "        return ''.join(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if(len(palindrome) <= 1):\n",
    "            return ''\n",
    "        palindrome = list(palindrome)\n",
    "        idx = None\n",
    "        m = len(palindrome)\n",
    "        for i in range(m//2):\n",
    "            if(palindrome[i] != 'a'):\n",
    "                idx = i\n",
    "                break\n",
    "        if(idx == None):\n",
    "            palindrome[-1] = 'b'\n",
    "        else:\n",
    "            palindrome[idx] = 'a'\n",
    "        return ''.join(palindrome)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        palindrome = list(palindrome)\n",
    "        Flag = False\n",
    "        for i in range(len(palindrome)//2):\n",
    "            if palindrome[i] != 'a':\n",
    "                palindrome[i] = 'a'\n",
    "                return ''.join(palindrome)\n",
    "        if len(palindrome) == 1:\n",
    "            return ''\n",
    "        else:\n",
    "            palindrome[len(palindrome)- 1] = 'b'\n",
    "            return ''.join(palindrome)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome) < 2:\n",
    "            return \"\"\n",
    "        cnt_map = collections.Counter(palindrome)\n",
    "\n",
    "        if palindrome[0] != 'a':\n",
    "            return ''.join(('a' if idx == 0 else c for idx, c in enumerate(palindrome)))\n",
    "        if len(cnt_map) == 1:\n",
    "            return ''.join(('b' if idx == len(palindrome) - 1 else 'a' for idx, c in enumerate(palindrome)))\n",
    "        idx_mid = len(palindrome) // 2\n",
    "        if len(cnt_map) == 2:\n",
    "            if cnt_map[palindrome[idx_mid]] == 1:\n",
    "                return ''.join(('b' if idx == len(palindrome) - 1 else c for idx, c in enumerate(palindrome)))\n",
    "            else:\n",
    "                return ''.join(('a' if idx == cnt_map['a'] / 2 else c for idx, c in enumerate(palindrome)))\n",
    "        idx_not_a = 0\n",
    "        while idx_not_a < len(palindrome):\n",
    "            if palindrome[idx_not_a] != 'a':\n",
    "                break\n",
    "            idx_not_a += 1\n",
    "        return ''.join(('a' if idx == idx_not_a else c for idx, c in enumerate(palindrome)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return \"\"\n",
    "        hwc = list(palindrome)\n",
    "        flag = False\n",
    "        for i in range(n//2 + 1):\n",
    "            if hwc[i] != 'a' and (n % 2 == 0 or n % 2 != 0 and i != n // 2):\n",
    "                hwc[i] = 'a'\n",
    "                flag = True\n",
    "                break\n",
    "        if not flag:\n",
    "            hwc[-1] = 'b'\n",
    "        return \"\".join(hwc)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        str_len = len(palindrome)\n",
    "        if str_len < 2:\n",
    "            return \"\"\n",
    "        for idx in range(str_len >> 1):\n",
    "            if palindrome[idx] > 'a':\n",
    "                return palindrome[:idx] + 'a' + palindrome[idx+1:]\n",
    "        return palindrome[:str_len-1] + 'b'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, p: str) -> str:\n",
    "        n=len(p)\n",
    "        if n==1: return ''\n",
    "        for i in range(n//2):\n",
    "            if p[i] != 'a':\n",
    "                return p[:i]+'a'+p[i+1:]\n",
    "        return p[:-1]+'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome) <= 1:\n",
    "            return ''\n",
    "        \n",
    "        n = len(palindrome)\n",
    "        for i in range(n):\n",
    "            if i * 2 != n - 1 and palindrome[i] != 'a':\n",
    "                return palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "        \n",
    "        return palindrome[:-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        result=''\n",
    "        n=len(palindrome)\n",
    "        if n<=1:\n",
    "            return \"\"\n",
    "        flag=False\n",
    "        for i in range(n//2):\n",
    "            if not palindrome[i]=='a':\n",
    "                result=palindrome[:i]+'a'+palindrome[i+1:]\n",
    "                flag=True\n",
    "                break\n",
    "            \n",
    "        if not flag:\n",
    "            result=palindrome[:n-1]+'b'\n",
    "        \n",
    "\n",
    "        return result\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome)==1:\n",
    "            return ''\n",
    "        for i in range(len(palindrome)):\n",
    "            if palindrome[i]!='a':\n",
    "                if len(palindrome)%2!=1 or i!=len(palindrome)//2:\n",
    "                    return palindrome[:i]+'a'+palindrome[i+1::]\n",
    "        return palindrome[:len(palindrome)-1]+'b'\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n < 2:\n",
    "            return ''\n",
    "        i = 0\n",
    "        while (i < n // 2):\n",
    "            if palindrome[i] != 'a':\n",
    "                return palindrome[:i] + 'a' + palindrome[i + 1:]\n",
    "            i += 1\n",
    "        \n",
    "        return palindrome[:-1] + 'b'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        s = list(palindrome)\n",
    "        if len(s)<=1:\n",
    "            return \"\"\n",
    "        n = len(s)\n",
    "        index = -1\n",
    "        for i,c in enumerate(s[:n//2]):\n",
    "            if c!='a':\n",
    "                index=i\n",
    "                break\n",
    "        if index<0:\n",
    "            s[-1] = 'b'\n",
    "        else:\n",
    "            s[index] = 'a'\n",
    "        return ''.join(s)\n",
    "    \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                w = chr(j+ord(\"a\"))\n",
    "                cur = palindrome[:i]+w+palindrome[i+1:]\n",
    "                if cur != cur[::-1] and (not ans or cur < ans):\n",
    "                    ans = cur\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, s: str) -> str:\n",
    "        if len(s) == 1:\n",
    "            return ''\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j and s[i] == 'a':\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if i < j:\n",
    "            return s[:i] + 'a' + s[i+1:]\n",
    "        else:\n",
    "            return s[:-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        p = list(palindrome)\n",
    "        l = len(p)\n",
    "        if l == 1:\n",
    "            return ''\n",
    "        for i in range(l//2):\n",
    "            if palindrome[i] != 'a':\n",
    "                p[i] = 'a'\n",
    "                return ''.join(p)\n",
    "        p[-1] = 'b'\n",
    "        return ''.join(p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        str_len = len(palindrome)\n",
    "        if str_len < 2:\n",
    "            return \"\"\n",
    "        for idx in range(str_len >> 1):\n",
    "            if palindrome[idx] > 'a':\n",
    "                return palindrome[:idx] + 'a' + palindrome[idx+1:]\n",
    "        return palindrome[:str_len-1] + 'b'\n",
    "        # str_len = len(palindrome)\n",
    "        # char_list = list(palindrome)\n",
    "        # for idx in range(str_len >> 1):\n",
    "        #     if char_list[idx] > 'a':\n",
    "        #         char_list[idx] = 'a'\n",
    "        #         return ''.join(char_list)\n",
    "        # char_list[str_len - 1] = 'b'\n",
    "        # return ''.join(char_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if(len(palindrome) <= 1):\n",
    "            return ''\n",
    "        palindrome = list(palindrome)\n",
    "        idx = None\n",
    "        m = len(palindrome)\n",
    "        for i in range(m//2):\n",
    "            if(palindrome[i] != 'a'):\n",
    "                idx = i\n",
    "                break\n",
    "        if(idx == None):\n",
    "            palindrome[-1] = 'b'\n",
    "        else:\n",
    "            palindrome[idx] = 'a'\n",
    "        return ''.join(palindrome)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        list=[]\n",
    "        num=0\n",
    "        for i in palindrome:\n",
    "            list.append(i)\n",
    "        for i in range(len(list)):\n",
    "            if list[i] ==\"a\":\n",
    "                num+=1\n",
    "        if list[0]!=list[len(list)-1] or len(list)==1:\n",
    "            return \"\"\n",
    "        if list[0]==list[1]==\"a\" and len(list)==2:\n",
    "            list[1]=\"b\"\n",
    "            return \"\".join(list)\n",
    "        if list[0]==list[len(list)-1]==\"a\" and len(list)%2==1 and num+1>=len(list):\n",
    "            list[len(list)-1]=\"b\"\n",
    "            return \"\".join(list)\n",
    "        for i in range(len(list)):\n",
    "            if list[i]==list[len(list)-1-i] and list[i]!=\"a\":\n",
    "                list[i]=\"a\"\n",
    "                break\n",
    "            \n",
    "\n",
    "       \n",
    "        \n",
    "        return \"\".join(list)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1: return \"\"\n",
    "        for i in range(n):\n",
    "            if palindrome[i] != 'a' and (n & 1 == 0 or i != n // 2):\n",
    "                return palindrome[:i] + 'a' + palindrome[i + 1:]\n",
    "        return palindrome[:-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Change the first char != 'a' to 'a', unless the char is at the middle of an odd-length palindrome.\n",
    "    If the palindrome consists of only 'a's, change the last char to 'b'.\n",
    "    Time complexity: O(n). Space complexity: O(1) (neglecting the output string).\n",
    "    '''\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return ''\n",
    "\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            if palindrome[i] != 'a':\n",
    "                if not (n % 2 != 0 and i == n // 2):\n",
    "                    return res + 'a' + palindrome[i+1:]\n",
    "            if i == n - 1:\n",
    "                return res + 'b'\n",
    "            res += palindrome[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "\n",
    "\n",
    "        n = len(palindrome)\n",
    "\n",
    "        if n < 2: return \"\"\n",
    "        for i in range(n >> 1):\n",
    "\n",
    "            if palindrome[i] > 'a':\n",
    "\n",
    "                return palindrome[:i] + 'a' + palindrome[i + 1:]\n",
    "        \n",
    "        return palindrome[:n - 1] + 'b'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome) <= 1:\n",
    "            return \"\"\n",
    "        \n",
    "        for i, char in enumerate(palindrome):\n",
    "            if char != 'a':\n",
    "                tmp = palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "                if tmp != tmp[::-1]:\n",
    "                    return tmp\n",
    "\n",
    "        return palindrome[:-1] + 'b'\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n<=1:\n",
    "            return ''\n",
    "        for i in range(n):\n",
    "            if palindrome[i] != 'a':\n",
    "                if i!= n-1:\n",
    "                    new_char = palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "                else:\n",
    "                    new_char = palindrome[:i] + 'a'\n",
    "                if (i < n//2 and new_char[n-1-i]=='a') or (i > n//2 and new_char[i] =='a') or i==n//2: \n",
    "                    break\n",
    "                return new_char\n",
    "            else:\n",
    "                continue\n",
    "        return palindrome[:(n-1)]+'b'\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        def isPalindrome(s:str):\n",
    "            for i in range(0,len(s) // 2):\n",
    "                if s[i] != s[len(s)-i-1]:\n",
    "                    return False\n",
    "            return True\n",
    "        if len(palindrome) == 1:\n",
    "            return \"\"\n",
    "        for i in range(0,(len(palindrome) + 1) // 2):\n",
    "            if palindrome[i] == \"a\":\n",
    "                continue\n",
    "            s = palindrome[:i] + \"a\" + palindrome[i+1:]\n",
    "            if not isPalindrome(s):\n",
    "                return s\n",
    "        return palindrome[:len(palindrome)-1] + \"b\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\r\n",
    "        str_len = len(palindrome)\r\n",
    "        if str_len < 2:\r\n",
    "            return \"\"\r\n",
    "        for idx in range(str_len >> 1):\r\n",
    "            if palindrome[idx] > 'a':\r\n",
    "                return palindrome[:idx] + 'a' + palindrome[idx+1:]\r\n",
    "        return palindrome[:str_len-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "\n",
    "        \"\"\"\n",
    "        首先如果字符串长度为奇数，则字符串中间的那个字符无论怎么改，字符串都是回文串。 \n",
    "        如：aba，b字符无论怎么改，字符串都还是回文串。\n",
    "\n",
    "        回文串前半段和后半段是相互对应的，因此只要遍历一半就好了。\n",
    "\n",
    "        1. 首先遍历前半段，遇到不为a的字符就直接将其替换成a，然后直接return结果。 \n",
    "        2. 如果前半段都是a，则说明后半段也都是a，说明字符串要么类似aabaa，要么类似aaaaaa。 直接将最后1个字符改成b就好了\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(palindrome)\n",
    "        if n < 2:\n",
    "            return \"\" # 1个字符始终是回文，无论怎么换\n",
    "\n",
    "        mid = n // 2\n",
    "        for i in range(mid):\n",
    "            if palindrome[i] > 'a':\n",
    "                return palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "        \n",
    "        return palindrome[:-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        i,j = 0,len(palindrome)-1\n",
    "        if i == j:\n",
    "            return ''\n",
    "        ls = list(palindrome)\n",
    "        while i <j:\n",
    "            if ls[i] != 'a':\n",
    "                ls[i] = 'a'\n",
    "                return ''.join(ls)\n",
    "            else:\n",
    "                i += 1\n",
    "                j-=1\n",
    "        ls[-1] = 'b'\n",
    "        return ''.join(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return ''\n",
    "        half = n // 2\n",
    "        for i in range(half):\n",
    "            if palindrome[i] != 'a':\n",
    "                return palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "        return palindrome[:n-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        lst = list(c for c in palindrome)\n",
    "        if n == 1:\n",
    "            return \"\"\n",
    "        for i in range(n // 2 + 1):\n",
    "            if i == n // 2:\n",
    "                lst[n - 1] = 'b'\n",
    "            else:\n",
    "                if lst[i] == 'a':\n",
    "                    continue\n",
    "                else:\n",
    "                    lst[i] = 'a'\n",
    "                    break\n",
    "        return ''.join(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        list=[]\n",
    "        num=0\n",
    "        for i in palindrome:\n",
    "            list.append(i)\n",
    "        for i in range(len(list)):\n",
    "            if list[i] ==\"a\":\n",
    "                num+=1\n",
    "        if list[0]!=list[len(list)-1] or len(list)==1:\n",
    "            return \"\"\n",
    "        if list[0]==list[1]==\"a\" and len(list)==2:\n",
    "            list[1]=\"b\"\n",
    "            return \"\".join(list)\n",
    "        if list[0]==list[len(list)-1]==\"a\" and len(list)%2==1 and num+1>=len(list):\n",
    "            list[len(list)-1]=\"b\"\n",
    "            return \"\".join(list)\n",
    "        for i in range(len(list)):\n",
    "            if list[i]==list[len(list)-1-i] and list[i]!=\"a\":\n",
    "                list[i]=\"a\"\n",
    "                break\n",
    "            \n",
    "\n",
    "       \n",
    "        \n",
    "        return \"\".join(list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if list(reversed(palindrome)) == list(palindrome):\n",
    "            lowerLetterSet = [ chr(i)for i in range(97,123)]\n",
    "            res = \"\"\n",
    "            # 算每个位置的最佳\n",
    "            for i in range(len(palindrome)):\n",
    "                for letter in lowerLetterSet:\n",
    "                    newStr = palindrome[:i] + letter + palindrome[i+1:]\n",
    "                    if list(newStr) != list(reversed(newStr)):\n",
    "                        \n",
    "                        res = min(res,newStr) if res else newStr\n",
    "                        break\n",
    "            \n",
    "            return res\n",
    "\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        str_len = len(palindrome)\n",
    "        if str_len < 2:\n",
    "            return \"\"\n",
    "        for idx in range(str_len >> 1):\n",
    "            if palindrome[idx] > 'a':\n",
    "                return palindrome[:idx] + 'a' + palindrome[idx+1:]\n",
    "        return palindrome[:str_len-1] + 'b'\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome) == 1:\n",
    "            return ''\n",
    "        if len(palindrome) % 2 == 1:\n",
    "            idx = len(palindrome) // 2\n",
    "        else:\n",
    "            idx = -1\n",
    "        for i in range(len(palindrome)):\n",
    "            if palindrome[i] != 'a' and i != idx:\n",
    "                return palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "            if i == len(palindrome)-1:\n",
    "                return palindrome[:i] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n < 2:\n",
    "            return \"\"\n",
    "        for i in range(n >> 1):\n",
    "            if palindrome[i] > 'a':\n",
    "                return palindrome[:i] + 'a' + palindrome[i+1:]\n",
    "        return palindrome[:n-1] + 'b'\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        list=[]\n",
    "        num=0\n",
    "        for i in palindrome:\n",
    "            list.append(i)\n",
    "        for i in range(len(list)):\n",
    "            if list[i] ==\"a\":\n",
    "                num+=1\n",
    "        if list[0]!=list[len(list)-1] or len(list)==1:\n",
    "            return \"\"\n",
    "        if list[0]==list[1]==\"a\" and len(list)==2:\n",
    "            list[1]=\"b\"\n",
    "            return \"\".join(list)\n",
    "        if list[0]==list[len(list)-1]==\"a\" and len(list)%2==1 and num+1>=len(list):\n",
    "            list[len(list)-1]=\"b\"\n",
    "            return \"\".join(list)\n",
    "        for i in range(len(list)):\n",
    "            if list[i]==list[len(list)-1-i] and list[i]!=\"a\":\n",
    "                list[i]=\"a\"\n",
    "                break\n",
    "            \n",
    "\n",
    "       \n",
    "        \n",
    "        return \"\".join(list)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n < 2:\n",
    "            return ''\n",
    "        for i in range(n // 2):\n",
    "            if palindrome[i] != 'a':\n",
    "                return palindrome[:i] + 'a' + palindrome[i + 1:]\n",
    "        \n",
    "        return palindrome[:-1] + 'b'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        L = len(palindrome)\n",
    "        if L<=1 :\n",
    "            return \"\"\n",
    "        iso = L%2\n",
    "        for i in range(0, L//2):\n",
    "            if palindrome[i] != 'a':\n",
    "                return palindrome[:i]+'a'+palindrome[i+1:]\n",
    "        return palindrome[:-1]+'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        str_len = len(palindrome)\n",
    "        if str_len < 2:\n",
    "            return \"\"\n",
    "        for idx in range(str_len >> 1):\n",
    "            if palindrome[idx] > 'a':\n",
    "                return palindrome[:idx] + 'a' + palindrome[idx+1:]\n",
    "        return palindrome[:str_len-1] + 'b'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1: return \"\"\n",
    "        palindrome = [e for e in palindrome]\n",
    "        flag = False\n",
    "        for i in range(n):\n",
    "            if palindrome[i]!='a' and not (n%2==1 and i==n//2):\n",
    "                palindrome[i] = 'a'\n",
    "                flag = True\n",
    "                break\n",
    "        if not flag:\n",
    "            palindrome[-1] = 'b'\n",
    "        return ''.join(palindrome)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return \"\"\n",
    "        arr = []\n",
    "        for x in palindrome:\n",
    "            arr.append(x)\n",
    "        flag = 0\n",
    "        for i in range(n // 2):\n",
    "            if palindrome[i] != 'a':\n",
    "                arr[i] = 'a'\n",
    "                flag = 1\n",
    "                break\n",
    "        if not flag:\n",
    "            arr[n - 1] = 'b'\n",
    "        palindrome = \"\"\n",
    "        for x in arr:\n",
    "            palindrome += x\n",
    "        return palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        if len(palindrome)==1:\n",
    "            return ''\n",
    "        for i in range(len(palindrome)):\n",
    "            if palindrome[i]!='a':\n",
    "                if len(palindrome)%2!=1 or i!=len(palindrome)//2:\n",
    "                    return palindrome[:i]+'a'+palindrome[i+1::]\n",
    "        return palindrome[:len(palindrome)-1]+'b'\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
